package binarytree

import "strconv"

// https://leetcode.cn/problems/binary-tree-paths/
// 思路：
// 1. 使用深度优先搜索（DFS）遍历二叉树。
// 2. 在遍历过程中维护当前路径。
// 3. 当到达叶子节点时，将当前路径添加到结果列表中。
func binaryTreePaths(root *TreeNode) []string {
	if root == nil {
		return nil
	}

	var paths []string
	var dfs func(node *TreeNode, path string)
	dfs = func(node *TreeNode, path string) {
		if node == nil {
			return
		}
		path += strconv.Itoa(node.Val)
		if node.Left == nil && node.Right == nil { // 叶子节点
			paths = append(paths, path)
		} else {
			path += "->" // 不是叶子节点，继续添加箭头
			dfs(node.Left, path)
			dfs(node.Right, path)
		}
	}

	dfs(root, "")
	return paths
}

func hasPathSum(root *TreeNode, targetSum int) bool {
	var dfs func(*TreeNode, int) bool
	dfs = func(node *TreeNode, sum int) bool {
		if node == nil {
			return false
		}
		sum += node.Val
		if node.Left == nil && node.Right == nil {
			return sum == targetSum
		}
		leftHas := dfs(node.Left, sum)
		rightHas := dfs(node.Right, sum)

		return leftHas || rightHas
	}

	return dfs(root, 0)
}

func FindBottomLeftValue(root *TreeNode) int {
	if root == nil {
		return 0
	}

	queue := []*TreeNode{root}
	var bottomLeftValue int

	for len(queue) > 0 {
		nextQueue := []*TreeNode{}     // 每一层都是用一个新的队列来存储下一层的节点，完美!!!
		bottomLeftValue = queue[0].Val // 每一层的第一个节点就是当前层的最左边节点

		for _, node := range queue {
			if node.Left != nil {
				nextQueue = append(nextQueue, node.Left)
			}
			if node.Right != nil {
				nextQueue = append(nextQueue, node.Right)
			}
		}
		queue = nextQueue
	}

	return bottomLeftValue
}
